#!/usr/bin/python
# -*- coding: iso-8859-15 -*-

def main(arr):
  """http://en.wikipedia.org/wiki/Maximum_subarray_problem"""
	max_ending_here = max_so_far = 0
	for x in arr:
		max_ending_here = max(x, max_ending_here + x)
		max_so_far = max(max_so_far, max_ending_here)
		print "max_ending_here : %s , max_so_far: %s " % (max_ending_here, max_so_far)
	print max_so_far

if __name__ == "__main__":
	#arr = [1,3,4,4,2,12,4,2,4]
	arr = [-2,1,-3,4,-1,2,1,-5,4]
	main(arr)